// 排序
// 排序稳定性：是指形相同元素在排序后是否还保持原来的位置，假如一个数组[2, 2, 1], 在排序后如果第二个2依然排在第一个2后面，则为稳定排序，否则为不稳定排序。

// 插入排序，把第一个元素视为有序数组，遍历数组依次将元素插入到前面的有序数组中。(长度小的数组表现更好)
function insertSort(arr) {
    for (let i = 1; i < arr.length; i++) {
        let ele = arr[i]    //要插入的元素
        let j
        for (j = i - 1; j >= 0; j--) {  //被插入的数组从后往前循环
            let cur = arr[j]
            if (cur > ele) {    // 当前元素大于被插入的元素，还需要往前查找
                arr[j + 1] = cur    // 元素需要在j的前面插入，被插入的数组j下标后面的所有元素都需要往后移位。
            } else {
                break
            }
        }
        arr[j + 1] = ele    // j-- 后跳出循环，j + 1找到跳出循环的位置插入ele。 后面的后排，如果当前元素不大于被插入的元素，则被插入的元素放到当前元素后面(稳定排序, 插入排序是最稳定的排序算法)
    }
    return arr
}
console.log(insertSort([6, 5, 6, 4, 8, 9, 1, 3]))

// 冒泡排序: 从第一个元素开始，一次与其他元素对比，如果有其他元素比当前小，则两个元素交换位置，直到最后一个元素。
function bubbleSort(arr) {
    for (let i = 0; i < arr.length; i++) {
        for (let j = i + 1; j < arr.length; j ++) {     // 不需要与前面的值做比较，因为前面已经排好。+ 1避免自身相比。
            if (arr[i] > arr[j]) {
                let ele = arr[j]
                arr[j] = arr[i]
                arr[i] = ele
            }
        }
    }
    return arr
}
console.log(bubbleSort([6, 5, 6, 4, 8, 9, 1, 3]))

// 快速排序
    // 1.选择一个元素作为基准(一般为中间的元素)
    // 2.小于基准的元素放到基准左边，大于基准的元素放到右边。
    // 3.对基准左边和右边的元素继续进行第一第二步操作，直到所有子集都只剩一个元素
function fastSort(arr) {
    if (arr.length <= 1) {  // 无需排序
        return arr
    }
    let piovt = arr.splice(Math.floor(arr.length / 2), 1)[0]    // 找到基准
    let left = []
    let right = []
    for (let i = 0; i < arr.length; i ++) {
        if (arr[i] < piovt) {
            left.push(arr[i])   // 小于基准点放在左边
        } else {
            right.push(arr[i])  // 大于基准点放在右边
        }
    }
    return fastSort(left).concat([piovt]).concat(fastSort(right))   // 对左边进行递归快排，对右边进行递归快排，并返回左边-基准-右边组成的数组。
}
console.log(fastSort([6, 5, 6, 4, 8, 9, 1, 3]))

// js V8用的排序算法：数组长度10以下的时候用插入排序，大于10的用快速排序。